package topic.a_array.a_erfen;

import java.util.Arrays;

public class ErfenSearch_704 {
    public static void main(String[] args) {
        /*
        给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
        写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
         */
        int[] arr = {1, 2, 3, 4, 7, 9, 10};
        System.out.println(search(arr, 9));
        System.out.println(search_2(arr, 9));
    }

    /*
    区间 左闭右闭 注意边界
     */
    public static int search(int[] s, int target) {
        int left = 0;
        int right = s.length - 1;  //定义target在左闭右闭区间
        Arrays.sort(s);
        while (left <= right) { //当left==right，区间[left, right]依然有效，所以用 <=
            int mid = left + ((right - left) / 2);
            if (s[mid] < target) {
                left = mid + 1;     //target在左区间，[left, mid + 1]
            } else if (s[mid] > target) {
                right = mid - 1;    //target在左区间，[left, mid - 1]
            } else {
                return mid;
            }
        }
        return -1;
    }

    /*
    方法 2 区间左闭右开
     */
    public static int search_2(int[] s, int target) {
        int left = 0;
        int right = s.length;   // 定义target在左闭右开的区间里，即：[left, right)
        while (left < right) {  // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
            int middle = left + ((right - left) >> 1);
            if (s[middle] > target) {
                right = middle;    // target 在左区间，在[left, middle)中
            } else if (s[middle] < target) {
                left = middle + 1; // target 在右区间，在[middle + 1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }

}
